/*
 * @lc app=leetcode.cn id=552 lang=cpp
 *
 * [552] 学生出勤记录 II
 */

// @lc code=start
class Solution {
public:
    const int MOD = 1e9 + 7, N = 100010;
    int f[100010][2][3];
    int checkRecord(int n) {
        //动态规划
        //每一次更新从当前状态可能达到的状态
        //f[i][j][k]表示长度为i，A的次数为i，末尾连续L的长度为k的方案数
        
        f[0][0][0] = 1;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < 2; j++)
                for(int k = 0; k < 3; k++){
                    //第i+1次是'A'
                    if(j < 1) f[i + 1][j + 1][0] = (f[i + 1][j + 1][0] + f[i][j][k]) % MOD;
                    //第i+1次是‘L’
                    if(k < 2) f[i + 1][j][k + 1] = (f[i + 1][j][k + 1] + f[i][j][k]) % MOD;
                    //第i+1次是'P'
                    f[i + 1][j][0] = (f[i + 1][j][0] + f[i][j][k]) % MOD;
                }
        
        int ans = 0;
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 3; k++)
                ans = (ans + f[n][j][k]) % MOD;
        return ans;
    }
};
// @lc code=end

